import java.util.Random;

public class Principal {
	public static void main (String [] args){
		Random r=new Random();
		int nDim,mDim;
		int [] nSoldados;
		int [] mSoldados;
		do {
			nDim=r.nextInt(6);
			nSoldados=new int [nDim];
			mDim=r.nextInt(6);
			mSoldados=new int [mDim];
		} while (nDim==0 && mDim==0);
		
		//rellenamos matrices
		for (int i=0;i<nDim;i++){
			nSoldados[i]=r.nextInt(37)+18;
		}
		
		for (int i=0;i<mDim;i++){
			mSoldados[i]=r.nextInt(37)+18;
		}
		
		utilidades.quicksort(nSoldados,0,nSoldados.length-1);
		utilidades.quicksort(mSoldados,0,mSoldados.length-1);
		
		utilidades.imprimir(nSoldados);
		utilidades.imprimir(mSoldados);
		
		int edad=posicionJonNieve (nSoldados,mSoldados);
		System.out.println("La edad postiza de John Nieve es: "+edad);
		int edad2[];
		
		if (nSoldados.length>0 && mSoldados.length>0){
			edad2=utilidades.merge(nSoldados,mSoldados);
		}
		else {
			if (nSoldados.length>0){
				edad2=nSoldados;
			}
			else {
				edad2=mSoldados;
			}
		}
		
		System.out.println();
		utilidades.imprimir(edad2);
		if (edad2.length%2==0){
			System.out.println("La edad deberia ser: "+edad2[((edad2.length-1)/2)]+" - "+edad2[((edad2.length)/2)]);
		}
		else {
			System.out.println("La edad deberia ser: "+edad2[((edad2.length)/2)]);
		}
	}
	
	public static int posicionJonNieve (int [] nSoldados, int [] mSoldados){
		int edad=posicionJonNieve_met (nSoldados,mSoldados,0,nSoldados.length-1,0,mSoldados.length-1);
		return edad;
	}
	
	private static int posicionJonNieve_met(int [] n,int [] m, int li1, int ls1, int li2, int ls2){
		int edad;
		
		int [] aux=new int [m.length];
		int aux2;
		if (n.length>m.length){
			aux=m;
			m=n;
			n=aux;
			
			aux2=li1;
			li1=li2;
			li2=aux2;
			
			aux2=ls1;
			ls1=ls2;
			ls2=aux2;
		}
		
		if (n.length<2){
			if (n.length==0 || m.length==1){
				edad=m[m.length/2];
			}
			else {
				if (m.length%2!=0){
					edad=m[m.length/2];
				}
				else {
					if (n[0]>m[m.length/2]){
						edad=m[m.length/2];
					}
					else {
						int med2men=m.length/2;
						if (m.length/2>0){
							med2men=m.length/2-1;
						}
						if (n[0]>m[med2men]){
							edad=n[0];
						}
						else {
							edad=m[med2men];
						}
					}
				}
			}
		}
		else {
			int med2=(li2+ls2)/2;
			int med1=(li1+ls1)/2;
			if (n[med1]==m[med2]){
				edad=m[med2];
			}
			else {
				if (ls1-li1==1){
					if (m[med2]>=n[ls1]){
						int med2men=med2;
						if (med2>0){
							med2men=med2-1;
						}
						if (m[med2men]>n[ls1]){
							edad=m[med2men];
						}
						else {
							edad=n[ls1];
						}
					}
					else {
						if (m[med2]>n[li1]){
							edad=m[med2];
						}
						else {
							int med2mas=med2;
							if (med2<m.length-1){
								med2mas=med2+1;
							}
							if (m[med2mas]>n[li1]){
								edad=n[li1];
							}
							else {
								edad=m[med2mas];
							}
						}
					}
				}
				else {
					if (n[med1]<m[med2]){
						li1=med1;
						ls2=m.length-med1-1;
					}
					else {
						ls1=med1;
						li2=n.length-med1-1;
					}
					edad=posicionJonNieve_met(n,m,li1,ls1,li2,ls2);
				}
			}
		}
		return edad;
	}
}
